#include <stdio.h>
#include <stdlib.h>

typedef struct LNode
{
    int data;
    LNode *next;
} LNode, *LinkList;

//无序单链表，删除s到t之间的结点
void Delete_s_t(LinkList &L, int s, int t)
{
    if (s > t)
    {
        int temp = t;
        t = s;
        s = temp;
    }

    if (L == NULL || L->next == NULL)
    {
        return;
    }

    LNode *p = L;
    LNode *q = L->next;

    while (q)
    {
        if (q->data >= s && q->data <= t)
        {
            q = q->next;
            free(p->next);
            p->next = q;
        }
        else
        {
            q = q->next;
            p = p->next;
        }
    }
    return;
}

//找到两个链表的公共结点
LNode *comElem(LinkList &L1, LinkList &L2)
{
    // 略略略 南瓜节哇嘎嘎 
    if (L1 || L2)
    {
        return NULL;
    }
    
    LNode *t = NULL, *p1 = L1->next, *p2 = L2->next;
    int length1 = 0;
    int length2 = 0;
    int temp = 0;

    while (p1)
    {
        length1 ++;
        p1 = p1->next;
    }

    while (p2)
    {
        length2 ++;
        p2 = p2->next;
    }
     if (length1 != length2)
     {
        temp = abs(length1-length2);
        p1 = L1->next;
        p2 = L2->next;
        if (length1 > length2)
        {
            for (int  i = 1; i <= temp; i++)
                p1 = p1->next;
        }
        else{
            for (int  i = 1; i <= temp; i++)
                p2 = p2->next;
        }
            
     }
    // while (p1->next != NULL)
    // {
    //     if(p1->next == p2->next){
    //         return p1;
    //     }
    //     else{
    //         p1 = p1->next;
    //         p2 = p2->next;
    //     }
    // }

    while (p1 != p2)
    {
        p1 = p1->next;
        p2 = p2->next;
    }
    
    return p1;
    
    

}

// 原地逆置
LNode *Reverse(LinkList &L)
{
    if (!L || !L->next)
        return;
    LNode *pre = NULL;
    LNode *cur = L;
    LNode *next;
    while (cur)
    {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

void Reverse2(LinkList &L)
{
    if (!L || !L->next)
        return;
    LNode *pre = NULL;
    LNode *cur = L->next;
    LNode *next;
    while (cur)
    {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    L->next = pre;
}

// 测试用

// 尾插法 并返回插入的节点
LNode *Append(LinkList head, int e)
{
    LNode *ptr = head;
    while (ptr->next)
    {
        ptr = ptr->next;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = NULL;
    ptr->next = s;
    return s;
}

// 遍历
void PrintForSingleList(LinkList head)
{
    LNode *ptr = head->next;
    printf("head->");
    while (ptr)
    {
        printf("%d->", ptr->data);
        ptr = ptr->next;
    }
    printf("null\n");
}

// 遍历 循环单链表
void PrintCircularlist(LinkList head)
{
    LNode *ptr = head->next;
    printf("head->");
    while (ptr != head)
    {
        printf("%d->", ptr->data);
        ptr = ptr->next;
    }
    printf("\n");
}

int main()
{
    LinkList head;
    // init
    head = (LNode *)malloc(sizeof(LNode));
    head->next = NULL;

    // append
    Append(head, 3);
    Append(head, 6);
    Append(head, 7);
    Append(head, 2);
    Append(head, 4);
    PrintForSingleList(head);

    LNode *newHead = Reverse(head->next);
    head->next = newHead;
    PrintForSingleList(head);

    Reverse2(head);
    PrintForSingleList(head);

    return 0;
}